There are a number of different kinds of flash memory; however, the present invention relates to what is generally known as NAND flash memory, and the term flash memory as used herein generally refers to NAND flash memory.
An important feature of flash memory devices is that they can maintain stored data without any external source of power. Thus, flash memory is frequently used in devices such as “thumb drives” and in digital cameras. A flash memory device can be removed from a computer or camera and the data stored in the device will not be lost.
The read operation in a flash memory is performed in a manner similar to the read operation in the older and less expensive Random Access (RAM) memories. However, the write operation in a flash memory is handled in a different manner from the way read operations are performed in RAM memories. In a RAM memory it is possible to write new data into individual memory locations that contain other data. This is not possible in a flash memory. New data cannot be written to a location in memory that already contains data. In a flash memory, a location must be erased before new data can be written to that location. Furthermore, an individual location in a flash memory can not be erased. Flash memories are divided into blocks and an erase operation is done on an entire block. Thus if data was previously stored in a block, the entire block containing a particular location must be erased before data can be written to any individual particular location within the block.
If a block of a flash memory contains data which is be preserved, prior to writing new data to a particular location in the block, any existing data in the entire block containing the particular location must be temporarily relocated. The reason for this is that the entire block must be erased in order to erase one particular location. Any existing data stored a block which one desires to preserve must be stored in some other location prior to the erase operation.
One type of widely used flash memory is called a Solid State Floppy Disk Card (SSFDC), or more commonly a SmartMedia™. The SmartMedia specifications were developed and they are maintained by the SSFDC Forum. The SmartMedia specifications are widely available. The SmartMedia specifications require that a memory must have twenty four temporary (already erased) blocks available for data storage.
With a standard SmartMedia device, there is a significant difference in the operations required to store a relatively small file (the size of which is twenty four, or less, blocks) and the operations required to store a file the size of which is larger than twenty four blocks. In order to store a file larger than twenty four blocks, one or more block erase operations must take place before the file write operation can be completed.
The following are examples that indicate the steps required for a typical write operation in a flash memory. It should be understood that these are merely examples and a wide variety of flash memory devices exist, each with its own individual characteristics.
The first example is a ‘best case’ situation where the file size exactly matches the flash memory block size. In most situations, this is an unlikely scenario; however, it can serve as a useful first example. In this example, no partial-block movement occurs. The memory controller merely identifies one of the empty blocks and writes the data into that block. Note that the SmartMedia specifications require that there be twenty four empty blocks available. After data storage is complete, the controller erases an unassigned block so that there will be twenty four erased blocks ready to receive data.
The second example is one where a small amount of data is being changed in a block that already contains data. This is a somewhat more realistic example. This example requires a partial-block movement operation. First the existing data which is not going to be changed is moved to one of the spare (previously erased) blocks. Next, the new data is added to the data in this block. After the storage operation is complete, the controller erases another block which is no longer assigned to a file.
The third example is an example that is particularly relevant to the present invention. In this example a file larger than the size of 24 blocks is written to the flash memory. First, the 24 spare blocks (which were previously erased) are filled with new data. Then the controller must locate other blocks that no longer have data that is being used and erase these blocks. Finally the additional data in the file is written to these newly erased blocks. Thus, the storage operation can not be completed until a relatively lengthy erase operation has been performed.
Host systems use a file allocation table (FAT) to record which logical addresses contain data related to each particular file. The present invention takes advantage of the fact that the FAT is stored in the flash memory. The FAT table indicates to the operating system which logical addresses are mapped to which files. At any particular time, any logical addresses that are not mapped to a file are not being used by any of the files stored in the memory. The memory controller maintains a table which correlates logical addresses to corresponding physical addresses.